package middle;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

public class Solution_306 {

    public static void main(String[] args) {
        Solution_306 model = new Solution_306();
        System.out.println(model.isAdditiveNumber("1999999999999999910000000000000000")); // true
        System.out.println(model.isAdditiveNumber("121474836472147483648")); // true
        System.out.println(model.isAdditiveNumber("198019823962")); // true
        System.out.println(model.isAdditiveNumber("11235813213455890144")); // false
        System.out.println(model.isAdditiveNumber("12012122436")); // true
        System.out.println(model.isAdditiveNumber("121224036")); // false
        System.out.println(model.isAdditiveNumber("1023")); // false
        System.out.println(model.isAdditiveNumber("112358")); // true
        System.out.println(model.isAdditiveNumber("199100199")); // true
//        System.out.println(Long.MAX_VALUE);
//        System.out.println(Integer.MAX_VALUE);
    }

    public boolean isAdditiveNumber(String num) {
        BigInteger[][] nums = new BigInteger[num.length()][num.length()];
        for (int i = 0; i < num.length(); i++) {
            for (int j = i; j < num.length(); j++) {
                nums[i][j] = new BigInteger(num.substring(i, j + 1));
            }
        }
        BigInteger[][] arrays = new BigInteger[num.length()][2];
        for (int i = 2; i < num.length(); i++) {
            for (int j = i-1; j >= 2; j--) {
                if (arrays[j] != null && arrays[j][0]!=null && arrays[j][1]!=null) {
                    BigInteger sum = nums[j+1][i];
                    if (arrays[j][0].add(arrays[j][1]).compareTo(sum) == 0 && num.charAt(j+1) != '0') {
                        arrays[i] = new BigInteger[]{arrays[j][1], sum};
                        break;
                    }
                }
            }
            if (arrays[i] == null || arrays[i][0]==null || arrays[i][1]==null) {
                for (int j = 0; j < i - 1; j++) {
                    for (int k = j + 1; k < i; k++) {
                        if (nums[0][j].add(nums[j + 1][k]).compareTo(nums[k + 1][i]) == 0
                            && (j == 0 || num.charAt(0) != '0')
                            && (j+1==k || num.charAt(j + 1) != '0')
                            && (k+1==i || num.charAt(k + 1) != '0')) {
                            arrays[i] = new BigInteger[]{nums[j + 1][k], nums[k + 1][i]};
                            break;
                        }
                    }
                }
            }
        }
        return arrays[num.length() - 1] != null && arrays[num.length() - 1][0]!=null && arrays[num.length() - 1][1]!=null;
    }

    private Set<Integer> dps(String num) {
        Set<Integer> set = new HashSet<>();
        if (num.length() == 0) {
            set.add(0);
            return set;
        }
        set.add(Integer.parseInt(num));
        for (int i = num.length() - 1; i >= 1; i--) {
            int sum = Integer.parseInt(num.substring(i));
            for (int j = i-1; j >= 0; j--) {
                int b = Integer.parseInt(num.substring(j, i));
                Set<Integer> dps = dps(num.substring(0, j));
                for (Integer a : dps) {
                    if (a + b == sum) {
                        set.add(sum);
                    }
                }
            }
        }
        return set;
    }
}
